package com.guqj.basis.datastruct.binarytree;

import java.util.Stack;

/**
 * 二叉树
 * 
 * @author guqj
 * @date 2017年3月29日
 */
public class BinaryTree {

	private TreeNode root;

	// 节点
	private static class TreeNode {
		private int data;
		private TreeNode left;
		private TreeNode right;

		public TreeNode(int e) {
			this.data = e;
			this.left = null;
			this.right = null;
		}
	}

	public BinaryTree() {
		this.root = null;
	}

	public TreeNode lookup(int data) {
		return lookup(root, data); // 从根节点开始找
	}

	public TreeNode lookup(TreeNode node, int data) {
		if (node == null) {
			return null;
		}
		if (data == node.data) { // 与当前节点相比较
			return node;
		} else if (data < node.data) { // 从左子树找
			return lookup(node.left, data);
		} else { // 从右子树找
			return lookup(node.right, data);
		}
	}

	public void insert(int data) {
		root = insert(root, data); // 从根节点开始
	}

	private TreeNode insert(TreeNode node, int data) {
		if (node == null) {
			node = new TreeNode(data);
		} else {
			if (data <= node.data) {
				node.left = insert(node.left, data);
			} else {
				node.right = insert(node.right, data);
			}
		}
		return node;
	}

	public int size() {
		return size(root);
	}

	private int size(TreeNode node) {
		if (node == null) {
			return 0;
		} else {
			return size(node.left) + 1 + size(node.right);
		}
	}

	// 二叉树的深度
	public int maxDepth() {
		return maxDepth(root);
	}

	private int maxDepth(TreeNode node) {
		if (node == null) {
			return 0;
		} else {
			int lDepth = maxDepth(node.left);
			int rDepth = maxDepth(node.right);
			return Math.max(lDepth, rDepth) + 1;
		}
	}

	// 二叉树的最小值
	public int minValue() {
		return minValue(root);
	}

	private int minValue(TreeNode node) {
		TreeNode current = node;
		while (current.left != null) {
			current = current.left;
		}
		return current.data;
	}

	// 二叉树的最大值
	public int maxValue() {
		return maxValue(root);
	}

	private int maxValue(TreeNode node) {
		TreeNode current = node;
		while (current.right != null) {
			current = current.right;
		}
		return current.data;
	}

	// 先序遍历 根节点->左子树->右子树
	public void printPreOrder() {
		printPreOrder(root);
	}

	private void printPreOrder(TreeNode node) {
		if (node == null) {
			return;
		}
		System.out.print(node.data + " ");
		printPreOrder(node.left);
		printPreOrder(node.right);
	}

	// 中序遍历 左子树->根节点->右子树
	public void printInOrder() {
		printInOrder(root);
	}

	private void printInOrder(TreeNode node) {
		if (node == null) {
			return;
		}
		printInOrder(node.left);
		System.out.print(node.data + " ");
		printInOrder(node.right);
	}

	// 后序遍历 左子树->右子树->根节点
	public void printPostOrder() {
		printPostOrder(root);
	}

	private void printPostOrder(TreeNode node) {
		if (node == null) {
			return;
		}
		printPostOrder(node.left);
		printPostOrder(node.right);
		System.out.print(node.data + " ");
	}

	/*
	 * public boolean del(){
	 * 
	 * }
	 */

	// ------------------- 非递归遍历 -----------------------
	// 先序遍历
	public void printNoRecPreOrder() {
		printNoRecPreOrder(root);
	}

	private void printNoRecPreOrder(TreeNode node) {
		Stack<TreeNode> stack = new Stack<>();
		TreeNode n = node;
		if (n == null) {
			return;
		}
		while (n != null) {
			System.out.print(n.data + " ");
			stack.push(n);
			n = n.left;
		}

		while (stack.size() > 0) {
			n = stack.pop();
			n = n.right;
			while (n != null) {
				System.out.print(n.data + " ");
				stack.push(n);
				n = n.left;
			}
		}
	}

	// 中序遍历
	public void printNoRecInOrder() {
		printNoRecInOrder(root);
	}

	private void printNoRecInOrder(TreeNode node) {
		Stack<TreeNode> stack = new Stack<>();
		TreeNode n = node;
		if (n == null) {
			return;
		}
		while (n != null) {
			stack.push(n);
			n = n.left;
		}

		while (stack.size() > 0) {
			n = stack.pop();
			if (n != null) {
				System.out.print(n.data + " ");
				n = n.right;
				while (n != null) {
					System.out.print(n.data + " ");
					stack.push(n.right);
					n = n.left;
				}
			}
		}
	}

	// 后序遍历
	public void printNoRecPostOrder() {
		printNoRecPostOrder(root);
	}

	public void printNoRecPostOrder(TreeNode node) {
		Stack<TreeNode> stack = new Stack<>();
		TreeNode n = node;

		while (node != null) {
			// 左子树入栈
			for (; node.left != null; node = node.left) {
				stack.push(node);
			}
			// 当前节点无右子或右子已经输出
			while (node != null && (node.right == null || node.right == n)) {
				System.out.print(node.data + " ");
				n = node;// 记录上一个已输出节点
				if (stack.empty()) {
					return;
				}
				node = stack.pop();
			}
			// 处理右子
			stack.push(node);
			node = node.right;
		}
	}

	// 镜子
	public void mirror() {
		mirror(root);
	}

	private void mirror(TreeNode node) {
		mirror(node.left);
		mirror(node.right);

		TreeNode temp = node.left;
		node.left = node.right;
		node.right = temp;
	}

	public static void main(String[] args) {
		BinaryTree tree = new BinaryTree();
		tree.insert(10);
		tree.insert(6);
		tree.insert(2);
		tree.insert(3);
		tree.insert(5);
		tree.insert(1);
		tree.insert(7);
		tree.insert(8);
		tree.insert(9);
		tree.insert(17);
		tree.insert(16);
		tree.insert(18);
		tree.insert(20);
		System.out.println("Tree size: " + tree.size());
		System.out.println("Tree max depth: " + tree.maxDepth());
		System.out.println("Tree min value: " + tree.minValue());
		System.out.println("Tree max value: " + tree.maxValue());
		System.out.println("*********** 先序遍历 *************");
		tree.printPreOrder();
		System.out.println("");
		System.out.println("*********** 中序遍历 *************");
		tree.printInOrder();
		System.out.println("");
		System.out.println("*********** 后序遍历 *************");
		tree.printPostOrder();
		System.out.println("");
		System.out.println("*********** 非递归先序遍历 *************");
		tree.printNoRecPreOrder();
		System.out.println("");
		System.out.println("*********** 非递归中序遍历 *************");
		tree.printNoRecInOrder();
		System.out.println("");
		System.out.println("*********** 非递归后序遍历 *************");
		tree.printNoRecPostOrder();
		System.out.println("");
	}
}
